// class Solution {
// public:
//     int majorityElement(vector<int>& nums) {
//         sort(nums.begin(), nums.end());
//         return nums[nums.size() / 2];
//     }
// };

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while (1) {
            int random = rand() % nums.size();
            int ans = nums[random];
            int count = 0;
            for (const auto& e : nums) {
                if (e == ans)
                    count++;
            }
            if (count > nums.size() / 2)
                return ans;
        }
    }
};